'''
https://leetcode.cn/problems/longest-palindromic-subsequence/description/
'''
from functools import cache

import numpy as np


class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        @cache
        def f(i, j):
            if i >= j:
                return 0
            if s[i] == s[j]:
                return 2 + f(i + 1, j - 1)
            return max(f(i + 1, j), f(i, j - 1) ) #, f(i + 1, j - 1))

        return f(0, len(s) - 1)

    def longestPalindromeSubseq2(self, s: str) -> int:
        n = len(s)
        # dp[i,j]依赖，左边和下边和左下
        dp = np.zeros((n, n), dtype=int)
        dp[-1, -1] = 1
        for i in range(n - 1):
            dp[i, i] = 1
            dp[i, i + 1] = 2 if s[i] == s[i+1] else 1
        print(dp)
        for i in range(n - 3, -1, -1):  # 最后一行，倒数第二行已经填完
            for j in range(i + 2, n):
                if s[i] == s[j]:
                    dp[i, j] = 2 + dp[i + 1, j - 1]
                else:
                    dp[i, j] = max(dp[i + 1, j], dp[i, j - 1], dp[i + 1, j - 1])
        return dp[0, n - 1].item()

    # 状态压缩
    def longestPalindromeSubseq3(self, s: str) -> int:
        n = len(s)
        # dp[i,j]依赖，左边和下边和左下
        A = np.zeros(n, dtype=int)
        A[-1] = 1
        for i in range(n - 2, -1, -1):
            B = np.zeros(n, dtype=int)
            B[i] = 1
            B[i+1] = 2 if s[i] == s[i+1] else 1
            for j in range(i + 2, n):
                if s[i] == s[j]:
                    B[j] = 2 + A[j - 1]
                else:
                    B[j] = max(A[j], B[j - 1])
            A = B
        return A[-1].item()
    def longestPalindromeSubseq4(self, s: str) -> int:
        n = len(s)
        # dp[i,j]依赖，左边和下边和左下
        A = [0] * n
        A[-1] = 1
        for i in range(n - 2, -1, -1):
            B = [0] * n
            B[i] = 1
            B[i+1] = 2 if s[i] == s[i+1] else 1
            for j in range(i + 2, n):
                if s[i] == s[j]:
                    B[j] = 2 + A[j - 1]
                else:
                    B[j] = max(A[j], B[j - 1])
            A = B
        return A[-1]


s = "cbbd"
print(Solution().longestPalindromeSubseq2(s))